Dynamic Programmig - Fibonacci

Method 1 - Recursion

Performance: O(2^N) -> Extreemly SLOW !!!

def fib_recursion(N):
    if N <= 1:
        return N
    return fib_recursion(N-1) + fib_recursion(N-2)

Method 2 - Loop

def fib_regular(N):
    if N == 0: return[0]
    if N == 1: return[0, 1]
    list = [0]
    i = 0
    first, next = 0, 1
    while i < N:
        list.append(next)
        first, next = next, first + next
        i += 1
    return list

Method 3 - Loop with generator

def gen_fib(N):
    a, b = 0, 1
    i = 0
    while i < N:
        a, b = b, a + b             # loop
        i += 1
        yield a                     # return

def fib_gen(N):
    if N == 0: return[0]
    if N == 1: return[0, 1]
    list = [0]
    for k in gen_fib(N):
        list.append((k))
    return list

Method 4 - Dynamic Programming

Perfomance O(N) -> Fast

def fib_dp(N):
    F = [0, 1] + [0]*(N-1)
    for i in range(2, N + 1):
        F[i] = F[i - 1] + F[i -2 ]
    return F[N]

Test

def test_fibo(fib_algorithm):

    print("Testing: ", fib_algorithm.__doc__)
    N = 10

    print("testcase #1: ", end="")
    A_exp = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
    if fib_algorithm.__doc__.strip() == "Fibonacci tree [recursion]":
        A_res = []
        for k in range(N + 1):
            A_res.append(fib_algorithm(k))
        # print(map(fib_algorithm, range(1, N)))
    else:
        A_res = fib_algorithm(N)
    print("Ok" if A_res == A_exp else "Fail")

if __name__ == "__main__":
    # Fibonnacci sequence
    test_fibo(fib_recursion)
    test_fibo(fib_regular)
    test_fibo(fib_gen)
    test_fibo(fib_dp)